package com.iqik.base.alg;

import java.util.ArrayList;

public class BaseDemo3 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left3 = new TreeNode(3);
        TreeNode left4 = new TreeNode(4);
        TreeNode left5 = new TreeNode(5);
        TreeNode left6 = new TreeNode(6);
        TreeNode left7 = new TreeNode(7);
        TreeNode left8 = new TreeNode(8);
        TreeNode left2 = new TreeNode(2);
        TreeNode right2 = new TreeNode(2);
        TreeNode right3 = new TreeNode(3);
        TreeNode right4 = new TreeNode(4);
        TreeNode right5 = new TreeNode(5);
        TreeNode right6 = new TreeNode(6);
        TreeNode right7 = new TreeNode(7);
        TreeNode right8 = new TreeNode(8);
//        left3.left = left5;
        left3.right = left6;
        left4.left = left7;
        left4.right = left8;
        left2.left = left3;
        left2.right = left4;
        right2.left = right4;
        right4.left = right8;
        right4.right = right7;
        right3.left = right6;
//        right3.right = right5;
        right2.right = right3;
        root.left = left2;
        root.right = right2;
        System.out.println(isTreeSymmetric(root));
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static boolean isTreeSymmetric(TreeNode root) {
        //TODO your code goes here...
        // 判断 root是否是kong
        if (root == null)
            return false;
        // 判断root是否是满二叉树
        if (root.left == null && root.right == null) return true;
//        if (!isFullTree(root))
//            return false;
        ArrayList<TreeNode> roots = new ArrayList<>();
        roots.add(root);
        while (root.left != null) {
            ArrayList<TreeNode> treeNodes = levelOrder(roots);
            int head = 0;
            int tail = treeNodes.size() - 1;
            while (head < tail) {
                if (treeNodes.get(head).val == treeNodes.get(tail).val) {
                    head += 1;
                    tail -= 1;
                } else {
                    return false;
                }
            }
            root = treeNodes.get(0);
            roots = treeNodes;
        }
        return true;
    }

    public static ArrayList<TreeNode> levelOrder(ArrayList<TreeNode> roots) {
        ArrayList<TreeNode> targets = new ArrayList<>();
        for (TreeNode root : roots) {
            targets.add(root.left);
            targets.add(root.right);
        }
        return targets;
    }

    public static boolean isFullTree(TreeNode root) {
        // 判断二叉树是否是满二叉树
        if(root==null){
            return false;
        }
        if(root.left==null&&root.right==null){
            return true;
        }
        int leftDepth = deep(root.left);
        int rightDepth = deep(root.right);
        if(leftDepth!=rightDepth){
            return false;
        }
        if(isFullTree(root.left) && isFullTree(root.right)){
            return true;
        }else{
            return false;
        }
    }

    public static int deep(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftDepth = deep(root.left);
        int rightDepth = deep(root.right);
        return rightDepth > leftDepth ? rightDepth + 1 : leftDepth + 1;
    }
}
